/**
 * @file filename.cpp
 * @brief nullptr关键字用于标识空指针，与NULL不同，NULL为0
 * @author Monomania (1301519350@qq.com)
 * @version 0.1
 * @date 2021-09-23
 */
#include<iostream>
#include <vector> 
#include <string>
#include <list>
#include <map>
#include <algorithm> // std::minmax_element
#include <boost/algorithm/string.hpp>
#include <functional>
#include <iterator>
// #define NDEBUG
#include <assert.h>
using namespace std;

#define OK 1
#define ERROR 0
#define TRUE true
#define FALSE false
// 定义一个不可能的数
#define INF   -99999  
#define MAXSIZE 20 /* 存储空间初始分配量 */

typedef int Status; 
typedef int SElemType; /* SElemType类型根据实际情况而定，这里假设为int */

struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

void visit_list(ListNode* head){
    ListNode* tmp = head;
    while(tmp != nullptr){
        cout << tmp->val << ' ';
        tmp = tmp->next;
    }
    cout << endl;
}


/** 解题思路
 * 由于数组中的元素都在 int（即 32 位整数）范围内，因此我们可以依次计算答案的每一个二进制位是 0 还是 1。
 * 
 * 考虑答案的第 i 个二进制位（i 从 0 开始编号），它可能为 0 或 1。
 * 对于数组中非答案的元素，每一个元素都出现了 3 次，对应着第 i 个二进制位的 3 个 0 或 3 个 1，无论是哪一种情况，它们的和都是 3 的倍数（即和为 0 或 3）
 * 
 */
class Solution {
    //将整数的各个数位上的加起来，然后对3取余，若结果为0，则待求数字在该位上是0；
    //若结果为1，则待求数字在该位上是1.
public:
    int singleNumber(vector<int>& nums) {
        int ans = 0;
        for (int i = 0; i < 32; ++i) {
            int total = 0;
            // 迭代容器中所有的元素---等价于：for (vector<int>::iterator iter = nums.begin(); iter != nums.end(); iter++)
            cout << "========" << i << "========" << endl;
            for (int num: nums) {
                total += ((num >> i) & 1);
                cout << num << " ";
            }
            cout << endl;
            cout << total << endl;
            if (total % 3) {
                ans |= (1 << i);
            }
        }
        return ans;
    }
};

// // 妙趣横生
// class Solution {
// public:
//     int singleNumber(vector<int>& nums) {
//         int one = 0,two = 0;
//         for(int x : nums){
//             one = ~two & (one ^ x);
//             two = ~one & (two ^ x);
//         }
//         return one;
//     }
// };



int main(int argc, const char** argv) {
    Solution solu = Solution();
    // vector<int> nums = {2,2,3,2};
    // vector<int> nums = {0,1,0,1,0,1,100};
    vector<int> nums = {30000,500,100,30000,100,30000,100};
    cout << solu.singleNumber(nums) << endl;

    return 0;
}